package com.coder.algorithm.leetcode

import com.coder.algorithm.struct.ListNode

/**
 * [160. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)
 *
 * @author yuhus
 * @date: 2022/3/31
 */
object l_0160 {
    fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
        if (headA == null || headB == null) {
            return null
        }
        var curA = headA
        var curB = headB
        while (curA != curB) {
            curA = if (curA == null) {
                headB
            } else {
                curA.next
            }
            if (curB == null) {
                curB = headA
            } else {
                curB = curB.next
            }
        }
        return curA
    }

    fun getIntersectionNode1(headA: ListNode?, headB: ListNode?): ListNode? {
        if (headA == null || headB == null) {
            return null
        }
        var curA = headA
        var curB = headB
        var chanagedCount = 0
        while (curA != null || curB != null) {
            // a b 可能长度一样
            if (curA == curB) {
                return curA
            }
            // 交换一次，多次交换变为死循环
            if (curA == null || curB == null) {
                if (chanagedCount == 2) {
                    return null
                }
                // 可能一样长，当不相交
                if (curA == null) {
                    curA = headB
                    chanagedCount++
                }
                if (curB == null) {
                    curB = headA
                    chanagedCount++
                }
            } else {
                curA = curA?.next
                curB = curB?.next
            }
        }
        return null
    }
}